package com.zk.algorithm.tree;

import com.zk.algorithm.Utils;
import com.zk.algorithm.annotation.LeetCodeExplore;
import com.zk.algorithm.annotation.Medium;
import com.zk.algorithm.bean.TreeLinkNode;
import com.zk.algorithm.factory.TreeFactory;

/**
 * 初始解法是利用 Queue，可是题目要求必须，Constance Space
 *
 * 参考
 * https://leetcode.com/explore/interview/card/top-interview-questions-medium/108/trees-and-graphs/789/discuss/37461/Java-solution-with-O(1)-memory+-O(n)-time
 */
@Medium
@LeetCodeExplore
public class PopulatingNextRightPointersInEachNode {

    public static void main(String...args) {
        PopulatingNextRightPointersInEachNode solution = new PopulatingNextRightPointersInEachNode();
        solution.connect(TreeFactory.buildLinkTree(new int[]{
                1,2,3,4,5,6,7
        }));
    }

//
//               1 -> NULL
//             /  \
//            2 -> 3 -> NULL
//          / \   / \
//         4->5->6->7 -> NULL
//
    public void connect(TreeLinkNode root) {
        TreeLinkNode p = root;

        while (p != null) {
            TreeLinkNode curr = p;

            // ========================
            // 一层
            // ========================
            while (curr != null) {

                // 左树.next = 右树
                // 2 -> 3
                if (curr.left != null) {
                    curr.left.next = curr.right;
                }

                // 右树.next = 下一个节点的.左树
                // 5 -> 6
                if (curr.right != null && curr.next != null) {
                    curr.right.next = curr.next.left;
                }

                // =====================
                // 在这一层走
                // =====================
                curr = curr.next;
            }

            p = p.left;
        }
    }

}